MOD = 10 ** 9 + 7


class Solution:
    def countVowelPermutation(self, n: int) -> int:
        dp1 = [1, 1, 1, 1, 1]
        for _ in range(n - 1):
            dp2 = [(dp1[1] + dp1[2] + dp1[4]) % MOD,
                   (dp1[0] + dp1[2]) % MOD,
                   (dp1[1] + dp1[3]) % MOD,
                   (dp1[2]) % MOD,
                   (dp1[2] + dp1[3]) % MOD]
            dp1 = dp2

        return sum(dp1) % MOD


if __name__ == "__main__":
    print(Solution().countVowelPermutation(1))  # 5
    print(Solution().countVowelPermutation(2))  # 10
    print(Solution().countVowelPermutation(5))  # 68
